using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
namespace Leet
{
    class P684
    {
        public static void Run()
        {
            var solution = new Solution();
            int[][] edges = null;
            Profiler.Run(solution.FindRedundantConnection, edges, ShowResult);
        }

        public static void ShowResult(int[] arr)
        {

        }
        public class Solution
        {
            class DisjointSetUnion
            {
                int[] rank, f;
                int n;

                public DisjointSetUnion(int n)
                {
                    this.n = n;
                    rank = new int[n];
                    Array.Fill(rank, 1);
                    f = new int[n];
                    for (int i = 0; i < n; i++)
                    {
                        f[i] = i;
                    }
                }

                public int FindRoot(int index)
                {
                    return f[index] == index ? index : FindRoot(f[index]);
                }

                public bool Set(int left, int right)
                {
                    left = FindRoot(left);
                    right = FindRoot(right);
                    if (left == right)
                    {
                        return false;
                    }

                    if (rank[left] < rank[right])
                    {
                        var t = left;
                        left = right;
                        right = left;
                    }

                    rank[left] = rank[right];
                    f[right] = left;

                    return true;
                }
            }
            public int[] FindRedundantConnection(int[][] edges)
            {
                DisjointSetUnion dis = new DisjointSetUnion(edges.Length + 10);
                foreach (var arr in edges)
                {
                    var left = arr[0];
                    var right = arr[1];

                    if (left > right)
                    {
                        var t = left;
                        left = right;
                        right = t;
                    }

                    if (!dis.Set(left, right))
                    {
                        return new int[] { left, right };
                    }
                }
                return null;
            }
        }
    }
}